// 节点类声明
export class Node<T> {
  val: T;
  next: Node<T> | null;
  constructor(value: T) {
    this.val = value;
    this.next = null;
  }
}

// 链表类声明
export class LinkedList<T> {
  protected length: number;
  protected dummy: Node<undefined>;
  protected head: Node<T> | null;
  protected next: Node<T> | null;
  // 构造函数
  constructor() {
    this.length = 0;
    this.dummy = new Node(void 0);
    this.head = null;
    this.dummy.next = this.head; // 哨兵节点插在头节点前
    this.next = null;
  }
  // 检查索引是否合理
  protected checkIndex(index: number): boolean {
    return index >= 0 && index < this.length;
  }
  // 插入节点
  insertToTail(val: T): void {
    if (this.head === null) {
      // 头节点为空
      this.head = new Node(val);
    } else {
      // 正常插入的情况
      let curr: Node<T> = this.head;
      while (curr.next !== null) {
        curr = curr.next;
      }
      curr.next = new Node(val); // 插到尾部
    }
    this.length++; //别忘了长度+1
  }
  // 根据索引找节点
  findNodeByIndex(index: number): Node<T> | null {
    if (!this.checkIndex(index)) {
      return null;
    } else {
      let curr: Node<T> | null = this.head;
      for (let i = 0; i < index && curr != null; i++) {
        curr = curr.next;
      }
      return curr;
    }
  }
  // 根据索引删除节点
  deleteByIndex(index: number): Node<T> | null {
    if (!this.checkIndex(index)) {
      return null;
    } else {
      let curr: Node<T> | null = this.head;
      if (index === 0) {
        // 如果是要删除头节点
        this.head = null;
      } else {
        const previous: Node<T> | null = this.findNodeByIndex(index - 1);
        curr = (previous != null ? previous.next : null);
        if (previous != null && curr != null) previous.next = curr.next;
      }
      this.length--;
      return curr;
    }
  }
  // 根据索引插入节点
  insertByIndex(index: number, val: T): boolean {
    if (index < 0 || index > this.length) {
      console.warn("请检查插入的索引是否合理。");
      return false;
    } else {
      // 边缘情况：需要插入头节点或尾节点
      if (index === 0 || index === this.length) {
        this.insertToTail(val);
        return true;
      } else {
        // 正常情况：在链表中部插入节点
        const previous: Node<T> | null = this.findNodeByIndex(index - 1); // 找前驱结点
        const curr = new Node(val);
        curr.next = (previous != null ? previous.next : null);
        if (previous != null) previous.next = curr;
        this.length++;
        return true;
      }
    }
  }
  // 根据值获取索引
  getIndexByVal(val: T): number {
    let curr: Node<T> | null = this.head;
    for (let i = 0; i < this.length && curr; i++) {
      if (curr.val === val) {
        return i;
      }
      curr = curr.next;
    }
    return -1;
  }
  // 获取链表长度
  getLength(): number {
    return this.length;
  }
  // 判断链表是否为空
  isEmpty(): boolean {
    return this.length === 0;
  }
  // 得到头节点
  getHead(): Node<T> | null {
    return this.head;
  }
  // 串行字符串化
  stringfy(): string {
    let str: string = "";
    let curr: Node<T> | null = this.head;
    for (let i = 0; i < this.length && curr; i++) {
      str = str + curr.val + "--->";
      curr = curr.next;
    }
    return str.slice(0, -4);// 删除最后的箭头
  }
}

// 测试用例
const linkedList = new LinkedList<number>();
linkedList.insertToTail(12);
linkedList.insertToTail(13);
linkedList.insertToTail(14);
linkedList.insertToTail(15);
linkedList.insertToTail(16);
linkedList.insertToTail(17);
linkedList.insertToTail(18);
linkedList.insertToTail(19);
// 移除索引为2的元素
linkedList.deleteByIndex(2);// 14
// 获取0号元素
console.log(linkedList.findNodeByIndex(0));// 12
// 查找19在链表中的位置
console.log(linkedList.getIndexByVal(19));// 6
// 在2号位置添加22元素
linkedList.insertByIndex(2, 22);
// 获取链表中的所有元素
console.log(linkedList.stringfy());
